package com.fulu.javabase.arithmetic.array;

import java.io.*;
import java.nio.CharBuffer;
import java.util.Arrays;

/**
 * 209. Minimum Size Subarray Sum
 * 中等
 * 1.8K
 * 相关企业
 * Given an array of positive integers nums and a positive integer target, return the minimal length of a
 * subarray
 *  whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
 *
 *  https://leetcode.cn/problems/minimum-size-subarray-sum/
 */
public class MinSubArrayLen {
    /**
     * O(n2log(n))
     * 超时
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        for (int len = 1; len <= nums.length; len++) {
            for (int i = 0; i < nums.length; i++) {
                int sum = 0;
                for (int j = i; j < i + len && j < nums.length; j++) {
                    sum += nums[j];
                }
                if(sum >= target){
                    return len;
                }
            }
        }
        return 0;
    }

    /**
     * 跟上面一样，超时
     * O(n2log(n))
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen1(int target, int[] nums) {
        int length = nums.length;
        if(length == 0) return 0;
        int winSize = 1;
        while (winSize <= length) {
            for (int i = 0; i < length - winSize + 1; i++) {
                int sum = 0;
                for (int j = 0; j < winSize; j++) {
                    sum += nums[i+j];
                }
                if(sum >= target){
                    return winSize;
                }
            }
            winSize++;
        }

        return 0;
    }

    public static int minSubArrayLen2(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    /**
     * O(n)
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen3(int target, int[] nums) {
        int length = nums.length;
        if(length == 0) return 0;
        int start = 0, end = 0;
        int ans = length + 1;
        int sum = 0;
        while (end < length){
            sum += nums[end];
            while (sum >= target){
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == length + 1 ? 0 : ans;
    }

    /**
     * 二分查找
     * O(n log(n))
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen4(int target, int[] nums) {
        // 元素都是正整数
        int length = nums.length;
        int min = Integer.MAX_VALUE;
        if(length == 0) return 0;
        if(length == 1){
            return nums[0] >= target ? 1 : 0;
        }
        int[] sums = new int[length + 1];
        for(int i = 1; i<= length; i++){
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for(int i = 0; i<= length; i++){
            int key = sums[i] + target;
            int index = Arrays.binarySearch(sums, key);
            if(index < 0){
                index = ~index;
            }
            if(index <= length) {
                min = Math.min(min, index - i);
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

    public static void main(String[] args) {
        try {
            //79517
            BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\work\\IdeaProjects\\fulu-narna\\javabase\\src\\main\\java\\com\\fulu\\javabase\\arithmetic\\array\\array.txt")));
            String s = reader.readLine();
            String[] split = s.split(",");
            int[] ints = Arrays.stream(split).mapToInt(Integer::parseInt).toArray();
//            int[] ints = new int[]{2,3,1,2,4,3};
//            int[] ints = new int[]{1,2,3,4,5};
//            int[] sums = new int[]{2,5,6,8,12,15};

            long start = System.currentTimeMillis();

            long end = System.currentTimeMillis();
            System.out.println(end - start + " ");
        } catch (Exception e) {
            e.printStackTrace();
        }

//        int i = minSubArrayLen(11, new int[]{1,2,3,4,5});
//        System.out.println(i);
    }
}
